public class QuickSort<Type extends Comparable<Type>> extends SorterParent<Type> {
	private Type[] toSort;

	@Override
	public Type[] sort(Type[] toSort, String method) {
		super.sort(toSort, method);
		this.toSort = toSort;
		doQuickSort(0, toSort.length -1);
		
		endTime = System.nanoTime();
		log.add("End of log. Nanotime is: " + endTime);
		
		return toSort;
	}

	public void doQuickSort(int low, int high) {
		int i = low;
		int j = high;
		Type pivot = getMedian(low, high);
		steps++;
		
		log.add("   Primary while-loop started \n");
		while (i <= j) {
			log.add("      Secondary while-loop started \n");
			while(toSort[i].compareTo(pivot) < 0) {
				i++;
				log.add("         i (help number) increased to " + i + ". \n");
			}
			while(toSort[j].compareTo(pivot) > 0) {
				j--;
				log.add("         j (help number) decreased to " + j + ". \n");
			}
			log.add("      Secondary while-loop ended \n");
			if(i <= j) {
				Type temp = toSort[i];
				toSort[i] = toSort[j];
				toSort[j] = temp;
				i++;
				j--;
				steps++;
			}
		}
		log.add("   Primary while-loop ended \n");
		if(low < j) {
			doQuickSort(low, j);
		}
		if(i < high) {
			doQuickSort(i, high);
		}
	}
	
	private Type getMedian(int low, int high) {
		Type first = toSort[low];
		Type mid = toSort[low + (high - low) / 2];
		Type last = toSort[high];

		if(first.compareTo(mid) >= 0) {
			if(mid.compareTo(last) >= 0) {
				return mid;
			} else if(first.compareTo(last) >= 0) {
				return last;
			} else {
				return first;
			}
		} else {
			if(first.compareTo(last) >= 0) {
				return first;
			} else if(mid.compareTo(last) >= 0) {
				return last;
			} else {
				return mid;
			}
		}
	}
}
